1. Field of the Invention
The present invention relates to technology for offering the optimum plans of multifarious planning problems in various fields. More particularly, it relates to a planning method of and a planning system for solving a problem which involves an enormous number of combinations or permutations and as to which a plan being the optimum solution exists without fail, with a simple construction and at a very high speed.
2. Description of the Related Art
In a variety of fields (for example, the design of the pattern to-be-printed of an electronic circuit board, a manufactural process, the design of piping in sewerage, and a materials handling system), various techniques have been proposed in order to find the optimum solutions within realistically allowable time periods in the planning of problems of multifarious purposes, wherein the optimum solutions are plans each of which maximize or minimize predetermined items.
By way of example, as stated in a report "Epoch-making Solution for `Traveling Salesman Problem`--Marvelously excellent results obtained by utilizing chaos" in a magazine "Kagaku Asahi (1993-Feb.)" or the official gazette of Japanese Patent Application Laid-open No. 304587/1990 entitled "System for Calculating Shortest Distance, Shortest Time or Lowest Traffic Cost", a mutual coupling type neural network, a chaotic technique, etc. are applied with the intention of realizing an expedient in which the plans of planning problems in various fields are optimized within actually allowable time periods.
In contrast to a so-called "enumeration method", wherein the combinations of all thinkable plans are studied on a given planning problem, recent optimization expedients which include the aforementioned example of the applications of the mutual coupling type neural network, the chaotic technique, etc. have a common idea as stated below. First, a certain plan is formed. Thenceforth, while the content of the plan is being efficiently altered little by little, the value of an objective function which expresses an item desired to be finally maximized or minimized in the planning problem is evaluated on and on (that is, plans are not formed at random, but the optimum solution is intended to be obtained in a small number of times of planning). Herein, a superior plan (for example, a plan which decreases the objective function value) is adopted as the succeeding candidate for the optimum plan, namely, the plan which maximizes or minimizes the objective function. Thus, it is intended to eventually obtain the optimum solution in a short time period.
Any of the prior-art techniques, however, have the following drawbacks:
(1) Each time a new plan is formed it requires at least n.sup.2 to n.sup.3 operation processes to be executed, in order to configure the new plan, where letter n denotes the number of the constituent elements (the objects to-be-dealt-with) of the particular plan. Herein, the constituent elements act as the parameter of the planning operation for optimizing the objective function. PA1 (2) There is not the theoretical support that the optimum solution can be reached, and the optimality is empirically evaluated. Accordingly, a long processing time period is expended in attaining to the optimum solution or a quasi-optimum solution. Moreover, the optimum solution is attained to at a very low probability. PA1 setting means for accepting, at least, a given planning problem, and values of a variable required for solving the problem; optimization means for creating an objective function which expresses an item intended for either of minimization and maximization in the planning problem, and for forming a plan which affords either of minimum and maximum values of the created objective function; and storage means for storing therein, at least, a variable required for forming the plan; PA1 the optimization means including calculation means for calculating a difference value between-values of the objective function assumed in a plan formed last and a plan formed anew; and replanning means for comparing the difference value of the objective function with a value of the variable previously set in the storage means, and for substituting the last formed plan by the plan formed this time and setting the latter as a candidate for the optimum plan, on condition that the difference value of the objective function is smaller than the value of the preset variable. PA1 altering part of an element arrayal of a permutation in a case where the plan is a permutation problem, and at least one element to-be-selected in a case where the plan is a combination problem; and PA1 calculating a difference between values of the objective function assumed before and after the alteration, and setting the new plan after the alteration as a candidate for an optimum plan on condition that the difference is smaller than a value which is uniformly distributed within a range of values decreasing gradually each time the plan is altered.
By way of example, in a system explained in the above report of the magazine, the settlement of the so-called "traveling salesman problem" for determining the shortest one of routes in each of which 30 places are respectively visited only once requires a long time period of 20 [seconds] even when a recent computer (for example, a work station having a capability of 10 to 100 [MIPS (million instructions per second)] is used. Besides, the optimum solution is erroneously found at a probability of 3 [%].